package 动态规划;

public class 环形子数组的最大和 {
    public int maxSubarraySumCircular(int[] nums) {
        // 分两种情况，一种为没有跨越边界的情况，一种为跨越边界的情况
        //没有跨越边界的情况直接求子数组的最大和即可；
        //跨越边界的情况可以对数组求和再减去无环的子数组的最小和，即可得到跨越边界情况下的子数组最大和；
        //求以上两种情况的大值即为结果，另外需要考虑全部为负数的情况
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        int ans1 = dp[0], ans2 = dp[0];
        for (int i = 1; i < n; i++){
            dp[i] =Math.max(nums[i], dp[i-1] + nums[i]);
            ans1 = Math.max(ans1, dp[i]);
        }
        int sum = dp[0];
        for (int i = 1; i < n; i++){
            sum += nums[i];
            dp[i] = Math.min(nums[i], dp[i-1] + nums[i]);
            ans2 = Math.min(ans2, dp[i]);
        }
        //全为负数
        if (sum == ans2)
            return ans1;
        return Math.max(ans1, sum - ans2);
    }
}
